//
//  ProblemMS0402.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/5/22.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 面试题 04.02. 最小高度树
 给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。

 示例:
 给定有序数组: [-10,-3,0,5,9],

 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

           0
          / \
        -3   9
        /   /
      -10  5
 */
@objcMembers class ProblemMS0402: NSObject {
    func solution() {
        let root = sortedArrayToBST([-10,-3,0,5,9])
        print(printNodeTree(root))
    }
    
    /*
     思路：让高度最小：就是让2边尽可能的平衡，那么我们取数组的中间节点为根节点
     1: 取 n/2处的节点为根节点，然后[left .. n/2) 做左节点，(n/2 .. right)做右节点
     2: 然后依次递归
     */
    func sortedArrayToBST(_ nums: [Int]) -> TreeNode? {
        return sortedArrayToBSTLR(nums, 0, nums.count-1)
    }
    
    func sortedArrayToBSTLR(_ nums: [Int], _ l: Int, _ r: Int) -> TreeNode? {
        if l > r {
            return nil
        } else if l == r {
            return TreeNode(nums[l])
        }
        
        let mid = l + (r - l) >> 1
        let root = TreeNode(nums[mid])
        if l < mid {
            root.left = sortedArrayToBSTLR(nums, l, mid-1)
        }
        if r > mid {
            root.right = sortedArrayToBSTLR(nums, mid+1, r)
        }
        return root
    }
}
